090 - Tenkei90's Last Problem（★7）
小課題1,2
$ K=1 なので数列には0と1しか置くことができない
また条件より1を2連続で置いてはいけない
このような置き方はフィボナッチ数列になるので、行列累乗で小課題2までの2点を取れる
小課題3~5
数列の値が0でない部分をブロックとして考える。
ブロックの最小値が$ x 以上で長さが$ yであるような通り数を求める。$ x=1 の場合が求められればDPで0を含む数列上での通り数も求められる。
$ x=K のときは明らかに$ y=1のときの1通りのみ。また$ yの上限は$ \lfloor \frac{K}{x} \rfloor となることにも注意。
ブロックの最小値が$ x-1以上の状態を考える。長さ$ yで全て$ x-1 で初期化したブロックを用意し、いくつかの区間を選んで最小値$ x以上のブロックに置き換えていく。このとき、配置したブロックが隣接してはいけない。（条件を破壊してしまうため）このような通り数は長さ$ yの右端にブロックを置かない場合、長さ$ 1,\cdots, y のブロックを置く場合としてDPで計算できる。
このパートの計算量は$ xが$ 1 \sim Kまで回り、$ y は$ K/xまで、そして各$ (x,y)について計算するのに$ K/x かかるので$ \sum K^2/i^2 = O(K^2) となる。（バーゼル問題）
長さ$ n数列の数え上げに関しても、最後の値を0にする/長さ$ yの1以上のブロックを配置する の2つに分けられるので、これもDPで計算できる。この計算量は$ O(NK)。
ここまでで7点が獲得できる。
小課題6
2つのDPの遷移をよく見ると線型漸化式と同じ形をしている。
線型漸化式$ a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots c_ka_{n-k} は$ Q(x)=1-c_1x-\cdots -c_kx^k として$ \frac{P(x)}{Q(x)} で表せる。($ P(x) は初項に関するk次未満の多項式)
よってそれぞれのDPの代わりに多項式除算を用いることで前者が$ O(k\log k\log k)、後者が$ N \log k で計算できる。
ここだけ知識 これができれば9点
満点
後者(線型漸化式の第$ N項)はBostan-Moriのアルゴリズムで$ O(k\log k \log N) で求められる。
自力で撃破できた
小課題5まではすぐできて、小課題6はBostan-Moriで調べながら線型漸化式と形式的冪級数の関係を学んだ